1. Field of the Invention
This invention relates generally to methods for evaluating mathematical functions of many variables, and more specifically to a tetrahedral linear interpolation method for approximating the value of a continuous multivariable function.
2. Description of the Prior Art
Many modern-day industrial processes require the evaluation of one or more mathematical functions. These functions frequently involve a multiplicity of variables interrelated by relatively complex mathematical expressions. Oftentimes, the overall efficiency of a process is determined by the relative ease or difficulty with which a function may be evaluated. For instance, in the field of color imaging, it is often desired to convert a color image from a first color space to a second color space. The first color space may be a pixel by pixel image representation stored in a computer file, and the second color space may be a color image created on paper by means of printer inks.
During the implementation of a process, it is generally more important to provide an efficient function evaluation technique, as opposed to providing a function evaluation technique optimized for maximum accuracy. For example, during the process of color image conversion, a quick, expedient evaluation of color image functions is much more important than a completely accurate representation of the converted color image. Efficiency is of paramount importance in this context because a common design goal of many image processing systems is to provide real-time processing capability. Accuracy is not a critical design parameter because the human eye can compensate for minor imaging errors. The characteristics of human visual perception generally allow for the existence of a known bounded error in image rendering. Although the importance of efficiency relative to accuracy has been described in conjunction with color imaging systems, a similar situation exists across a broad spectrum of other process applications as well.
In some process applications, the output of a function may be sampled, but the function itself is unknown. For example, consider the conversion of an image from the color space of a computer file to the surface of a newspaper. The actual colors produced by the printing ink interacting with the paper are difficult or impossible to accurately quantize. The factors resulting in the appearance of a given color on paper are represented by an unknown function, even though the value of the function can be sampled at various intervals. In this scenario, an accurate representation of the imaging information is not at all critical, and emphasis may instead be placed on data processing speed.
Many existing processes involve mathematical functions having extensive domains. It is generally impractical to sample the output of the function at all possible domain values. For example, FIG. 1 illustrates the domain of a mathematical function representing the color of an object in the context of a color image processing system. State of the art color imaging systems represent a color image as a regular array of spots, generally referred to as pixels. Each pixel is assigned a color represented by the coordinates of the color in a three dimensional space. In an additive color environment (i.e., a cathode-ray tube display), any color may be represented by a given combination of the three primary colors of red, green, and blue. The value of red may be represented, for example, along the X axis, green along the Y axis, and blue along the Z axis. Each coordinate may be of arbitrary precision, but coordinates are generally represented using 8-bit values. In this manner, each pixel may be assigned one of 2.sup.24 different colors. Therefore, the domain of the mathematical function representing pixel color is quite extensive.
The mathematical function accepts input values within the domain of the function, and produces output values corresponding to the input values. The sequence of mathematical operations carried out by the function is determined by the process to be implemented. To print a color image displayed on a cathode-ray tube, the image must be converted from additive to subtractive form. As previously described, the cathode-ray tube image is stored as a pixel-by-pixel representation specifying particular quantities of the colors red, green, and blue. For subtractive color applications, such as printing, the three primary colors are magenta, yellow, and cyan (blue-green). In printing, the range of colors that can be realized is often extended by using black. Accordingly, a function must be determined for the purpose of converting pixel color representations into known quantities of colored printer inks, typically with the amount expressed as an integer in the range of 0 to 255 for each of cyan, yellow, magenta, and black. The function accepts input values for the variables red, green and blue, and produces output values which represent quantities of magenta, yellow, cyan, and black.
For many processes, it is highly impractical to define a function in analytical form. In the context of color image conversion, it would be very difficult to develop a working analytical model for the purpose of converting a cathode-ray tube image representation into a form suitable for color printing on newspaper media. If the printer inks offered a perfectly linear response, and if the paper was perfectly white, then the function for the conversion of the color image could be specified analytically. However, as a practical matter, the inks have a nonlinear response, and the paper is off-white. Consequently, the print function is best represented by using measurements accumulated form a plurality of print samples. There are 2.sup.24 points in the function domain which could be sampled, so it would be prohibitively time-consuming to measure and store all of these values. Rather, the function may be approximated using a smaller set of measured values (sample points), and using interpolation to compute the approximate values for all of the other domain values.
FIG. 1 illustrates the concept of taking sample points at regularly-spaced intervals throughout the display-color space, which is the domain of the print-color function. Each sample point is represented by an ordered triplet (RGB) which corresponds to values along the red (R), green (G), and blue (B) axes of display-color space. Samples are taken at points 18, 20, 22, 24, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, and 48. In this manner, the sample points form a rectangular grid throughout the domain of the function. The rectangular grid is comprised of a plurality of rectangular volumes 10.
One advantageous interpolation technique is known as tetrahedral linear interpolation. This technique is often selected in preference to other methods of approximating a function because it requires fewer arithmetic operations to compute an approximation. The reduced number of steps required to execute tetrahedral interpolation has important practical consequences, in that less hardware is required, and the computational steps may be implemented faster and more efficiently.
The process of linear interpolation is used to approximate the value of a function of n variables at n+1 points p, over the domain of the function, by sampling the value v of the function at predetermined intervals. In the case of tetrahedral interpolation, the domain of the function is divided up into a plurality of tetrahedral volumes.
The process of dividing the function domain in this manner is often a two-step procedure. Typically, the domain is first divided into rectangular solids as shown in FIG. 1, and then each of the rectangular solids so created is then subdivided into a plurality of tetrahedra.
FIG. 2 sets forth an illustrative example of dividing a function domain 112 into tetrahedral volumes. A rectangular solid 10 is shown, corresponding to any one of the rectangular solids of FIG. 1. The rectangular solid 10 is subdivided into five tetrahedra 200, 202, 204, 206, and 208. Although the geometrical configuration of FIG. 2 illustrates the division of a rectangular volume into five tetrahedra, it is also possible to divide the rectangular volume into another number of tetrahedral structures. For example, the rectangular solids are often divided into six or twelve tetrahedra, and the methods used to accomplish such division are well-known to those skilled in the art.
FIG. 3 is a perspective view illustrating the geometrical structure of a tetrahedron shown in FIG. 2. The tetrahedron 12 is a geometric solid having four planar faces 302, 304, 306, and 308, six edges a-a', b-b', c-c', d-d', e-e', and f-f' and four vertices 310, 312, 314, and 316. Relatedly, each vertex corresponds to a sample point in the function domain space.
To approximate the value v of the function at any arbitrarily selected point p along the function domain, the tetrahedron containing the selected point must be determined. The function values v at the four vertices 310, 312, 314, and 316 of the selected tetrahedron are sampled, and a standard three dimensional linear interpolation procedure may be applied to the function values v to calculate an approximation for the function value v at the point p. In this manner, it is not necessary to obtain sample values for the function value v at all points along the function domain. The standard method of computing an approximated value uses the formula ##EQU2## where v.sub.i is the function value at vertex i of the tetrahedron containing the point p at which an approximation is desired. The coefficients u.sub.i are computed from the coordinates of the vertices and of the point p.
For a function of n variables at n+1 points, the standard linear interpolation procedure requires the performance of n+1 multiplication steps and n addition steps. The performance of each of these steps in a processor or computer consumes valuable hardware resources, and increases the time required to calculate an approximation. Consequently, it would be very desirable to reduce the overall number of operations required to implement tetrahedral linear interpolation. Multiplication steps should be avoided wherever possible, as these steps are much more expensive to implement than additions. Accordingly, it would be especially desirable to reduce the number of multiplication operations required to approximate a function value using a processor performing tetrahedral interpolation.
A method of computing a tetrahedral interpolation function is described in "Color Correction Technique for Hard Copies by 4-Neighbors Interpolation Method", Journal of Imaging Science and Technology, Vol. 36:1, January-February 1992, by Katsuhiro Kanamori and Kiroaki Kotera. This method discloses ##EQU3## to compute an approximation for the function value (CMY) which corresponds to the colors cyan, magenta, and yellow, respectively. This formula represents one of the final steps in computing a function approximation.
The above formula is only applicable in the case of a function having both a three-dimensional input and a three-dimensional output. Quite frequently, however, it is desired to convert a standard Red-Green-Blue (RGB) video image into a Cyan-Magenta-Yellow-Black (CMYB) printed image. Alternatively, it may be desired to process image information received from a plurality of electromagnetic sensors, wherein each sensor is responsive to a different range of frequencies in the electromagnetic spectrum. If the output of each sensor is conceptualized as representing a given dimension, such an imaging system may require the performance of calculations in a number of dimensions greater than three. What is needed is a function approximation method which is capable of being utilized in conjunction with multidimensional functions where the domain inputs, range outputs or both, represent three or more dimensions.